//
// Created by francklinson on 2021/5/22.
//

//中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
//
//例如，
//
//[2,3,4]的中位数是 3
//
//[2,3] 的中位数是 (2 + 3) / 2 = 2.5
//
//设计一个支持以下两种操作的数据结构：
//
//void addNum(int num) - 从数据流中添加一个整数到数据结构中。
//double findMedian() - 返回目前所有元素的中位数。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/find-median-from-data-stream
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
// 同 MedianFinder
#include <queue>
#include <iostream>

using namespace std;

class MedianFinder {
private:
    priority_queue<int> lMaxHeap;
    priority_queue<int, vector<int>, greater<>> rMinheap;
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }

    void addNum(int num) {
        // 默认左边多
        if (lMaxHeap.size() != rMinheap.size()) {
            // 左边多
            // 新增的数先进左边，左边的最大值进右边
            lMaxHeap.push(num);
            rMinheap.push(lMaxHeap.top());
            lMaxHeap.pop();
        } else {
            // 左右一样多，先进右边，右边的最小值进左边
            rMinheap.push(num);
            lMaxHeap.push(rMinheap.top());
            rMinheap.pop();
        }
    }

    double findMedian() {
        return lMaxHeap.size() == rMinheap.size() ? (double) (lMaxHeap.top() + rMinheap.top()) / 2 :
               (double) lMaxHeap.top();
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

int main() {
    auto obj = new MedianFinder;
    obj->addNum(1);
    obj->addNum(2);
    cout << obj->findMedian() << endl;
    obj->addNum(3);
    cout << obj->findMedian() << endl;
    return 0;
}